/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 *    RandomProjection.java
 *    Copyright (C) 2003-2012 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.filters.unsupervised.attribute;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Random;
import java.util.Vector;

import weka.core.Attribute;
import weka.core.Capabilities;
import weka.core.Capabilities.Capability;
import weka.core.DenseInstance;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.Randomizable;
import weka.core.SelectedTag;
import weka.core.Tag;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;
import weka.core.WeightedInstancesHandler;
import weka.filters.Filter;
import weka.filters.UnsupervisedFilter;

/**
 * <!-- globalinfo-start --> Reduces the dimensionality of the data by
 * projecting it onto a lower dimensional subspace using a random matrix with
 * columns of unit length. It will reduce the number of attributes in the data
 * while preserving much of its variation like PCA, but at a much less
 * computational cost.<br/>
 * It first applies the NominalToBinary filter to convert all attributes to
 * numeric before reducing the dimension. It preserves the class attribute.<br/>
 * <br/>
 * For more information, see:<br/>
 * <br/>
 * Dmitriy Fradkin, David Madigan: Experiments with random projections for
 * machine learning. In: KDD '03: Proceedings of the ninth ACM SIGKDD
 * international conference on Knowledge discovery and data mining, New York,
 * NY, USA, 517-522, 003.
 * <p/>
 * <!-- globalinfo-end -->
 * 
 * <!-- technical-bibtex-start --> BibTeX:
 * 
 * <pre>
 * &#64;inproceedings{Fradkin003,
 *    address = {New York, NY, USA},
 *    author = {Dmitriy Fradkin and David Madigan},
 *    booktitle = {KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining},
 *    pages = {517-522},
 *    publisher = {ACM Press},
 *    title = {Experiments with random projections for machine learning},
 *    year = {003}
 * }
 * </pre>
 * <p/>
 * <!-- technical-bibtex-end -->
 * 
 * <!-- options-start --> Valid options are:
 * <p/>
 * 
 * <pre>
 *  -N &lt;number&gt;
 *  The number of dimensions (attributes) the data should be reduced to
 *  (default 10; exclusive of the class attribute, if it is set).
 * </pre>
 * 
 * <pre>
 *  -D [SPARSE1|SPARSE2|GAUSSIAN]
 *  The distribution to use for calculating the random matrix.
 *  Sparse1 is:
 *    sqrt(3)*{-1 with prob(1/6), 0 with prob(2/3), +1 with prob(1/6)}
 *  Sparse2 is:
 *    {-1 with prob(1/2), +1 with prob(1/2)}
 * </pre>
 * 
 * <pre>
 *  -P &lt;percent&gt;
 *  The percentage of dimensions (attributes) the data should
 *  be reduced to (exclusive of the class attribute, if it is set). The -N
 *  option is ignored if this option is present and is greater
 *  than zero.
 * </pre>
 * 
 * <pre>
 *  -M
 *  Replace missing values using the ReplaceMissingValues filter instead of just skipping them.
 * </pre>
 * 
 * <pre>
 *  -R &lt;num&gt;
 *  The random seed for the random number generator used for
 *  calculating the random matrix (default 42).
 * </pre>
 * 
 * <!-- options-end -->
 * 
 * @author Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)
 * @version $Revision$ [1.0 - 22 July 2003 - Initial version (Ashraf M.
 *          Kibriya)]
 */
public class RandomProjection extends Filter implements UnsupervisedFilter, OptionHandler, TechnicalInformationHandler, Randomizable, WeightedInstancesHandler {

    /** for serialization */
    static final long serialVersionUID = 4428905532728645880L;

    /** Stores the number of dimensions to reduce the data to */
    protected int m_k = 10;

    /**
     * Stores the dimensionality the data should be reduced to as percentage of the
     * original dimension
     */
    protected double m_percent = 0.0;

    /** distribution type: sparse 1 */
    public static final int SPARSE1 = 1;
    /** distribution type: sparse 2 */
    public static final int SPARSE2 = 2;
    /** distribution type: gaussian */
    public static final int GAUSSIAN = 3;

    /**
     * The types of distributions that can be used for calculating the random matrix
     */
    public static final Tag[] TAGS_DSTRS_TYPE = { new Tag(SPARSE1, "Sparse1"), new Tag(SPARSE2, "Sparse2"), new Tag(GAUSSIAN, "Gaussian"), };

    /**
     * Stores the distribution to use for calculating the random matrix
     */
    protected int m_distribution = SPARSE1;

    /**
     * Should the missing values be replaced using unsupervised.ReplaceMissingValues
     * filter
     */
    protected boolean m_useReplaceMissing = false;

    /** Keeps track of output format if it is defined or not */
    protected boolean m_OutputFormatDefined = false;

    /** The NominalToBinary filter applied to the data before this filter */
    protected Filter m_ntob;

    /** The ReplaceMissingValues filter */
    protected Filter m_replaceMissing;

    /** Stores the random seed used to generate the random matrix */
    protected int m_rndmSeed = 42;

    /** The random matrix */
    protected double m_rmatrix[][];

    /** The random number generator used for generating the random matrix */
    protected Random m_random;

    /**
     * Returns an enumeration describing the available options.
     * 
     * @return an enumeration of all the available options.
     */
    @Override
    public Enumeration<Option> listOptions() {

        Vector<Option> newVector = new Vector<Option>(5);

        newVector.addElement(new Option("\tThe number of dimensions (attributes) the data should be reduced to\n" + "\t(default 10; exclusive of the class attribute, if it is set).", "N", 1, "-N <number>"));

        newVector.addElement(new Option("\tThe distribution to use for calculating the random matrix.\n" + "\tSparse1 is:\n" + "\t  sqrt(3)*{-1 with prob(1/6), 0 with prob(2/3), +1 with prob(1/6)}\n" + "\tSparse2 is:\n" + "\t  {-1 with prob(1/2), +1 with prob(1/2)}", "D", 1, "-D [SPARSE1|SPARSE2|GAUSSIAN]"));

        // newVector.addElement(new Option(
        // "\tUse Gaussian distribution for calculating the random matrix.",
        // "G", 0, "-G"));

        newVector.addElement(new Option("\tThe percentage of dimensions (attributes) the data should\n" + "\tbe reduced to (exclusive of the class attribute, if it is set). The -N\n" + "\toption is ignored if this option is present and is greater\n" + "\tthan zero.", "P", 1, "-P <percent>"));

        newVector.addElement(new Option("\tReplace missing values using the ReplaceMissingValues filter instead of just skipping them.", "M", 0, "-M"));

        newVector.addElement(new Option("\tThe random seed for the random number generator used for\n" + "\tcalculating the random matrix (default 42).", "R", 0, "-R <num>"));

        return newVector.elements();
    }

    /**
     * Parses a given list of options.
     * <p/>
     * 
     * <!-- options-start --> Valid options are:
     * <p/>
     * 
     * <pre>
     *  -N &lt;number&gt;
     *  The number of dimensions (attributes) the data should be reduced to
     *  (default 10; exclusive of the class attribute, if it is set).
     * </pre>
     * 
     * <pre>
     *  -D [SPARSE1|SPARSE2|GAUSSIAN]
     *  The distribution to use for calculating the random matrix.
     *  Sparse1 is:
     *    sqrt(3)*{-1 with prob(1/6), 0 with prob(2/3), +1 with prob(1/6)}
     *  Sparse2 is:
     *    {-1 with prob(1/2), +1 with prob(1/2)}
     * </pre>
     * 
     * <pre>
     *  -P &lt;percent&gt;
     *  The percentage of dimensions (attributes) the data should
     *  be reduced to (exclusive of the class attribute, if it is set). The -N
     *  option is ignored if this option is present and is greater
     *  than zero.
     * </pre>
     * 
     * <pre>
     *  -M
     *  Replace missing values using the ReplaceMissingValues filter instead of just skipping them.
     * </pre>
     * 
     * <pre>
     *  -R &lt;num&gt;
     *  The random seed for the random number generator used for
     *  calculating the random matrix (default 42).
     * </pre>
     * 
     * <!-- options-end -->
     * 
     * @param options the list of options as an array of strings
     * @throws Exception if an option is not supported
     */
    @Override
    public void setOptions(String[] options) throws Exception {

        String mString = Utils.getOption('P', options);
        if (mString.length() != 0) {
            setPercent(Double.parseDouble(mString));
        } else {
            setPercent(0);
            mString = Utils.getOption('N', options);
            if (mString.length() != 0) {
                setNumberOfAttributes(Integer.parseInt(mString));
            } else {
                setNumberOfAttributes(10);
            }
        }

        mString = Utils.getOption('R', options);
        if (mString.length() != 0) {
            setSeed(Integer.parseInt(mString));
        }

        mString = Utils.getOption('D', options);
        if (mString.length() != 0) {
            if (mString.equalsIgnoreCase("sparse1")) {
                setDistribution(new SelectedTag(SPARSE1, TAGS_DSTRS_TYPE));
            } else if (mString.equalsIgnoreCase("sparse2")) {
                setDistribution(new SelectedTag(SPARSE2, TAGS_DSTRS_TYPE));
            } else if (mString.equalsIgnoreCase("gaussian")) {
                setDistribution(new SelectedTag(GAUSSIAN, TAGS_DSTRS_TYPE));
            }
        }

        if (Utils.getFlag('M', options)) {
            setReplaceMissingValues(true);
        } else {
            setReplaceMissingValues(false);
        }

        Utils.checkForRemainingOptions(options);
    }

    /**
     * Gets the current settings of the filter.
     * 
     * @return an array of strings suitable for passing to setOptions
     */
    @Override
    public String[] getOptions() {

        Vector<String> options = new Vector<String>();

        if (getReplaceMissingValues()) {
            options.add("-M");
        }

        if (getPercent() <= 0) {
            options.add("-N");
            options.add("" + getNumberOfAttributes());
        } else {
            options.add("-P");
            options.add("" + getPercent());
        }

        options.add("-R");
        options.add("" + getSeed());

        SelectedTag t = getDistribution();
        options.add("-D");
        options.add("" + t.getSelectedTag().getReadable());

        return options.toArray(new String[0]);
    }

    /**
     * Returns a string describing this filter
     * 
     * @return a description of the filter suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String globalInfo() {

        return "Reduces the dimensionality of the data by projecting" + " it onto a lower dimensional subspace using a random" + " matrix with columns of unit length. It will reduce" + " the number of attributes in the data while preserving" + " much of its variation like PCA, but at a much less" + " computational cost.\n" + "It first applies the NominalToBinary filter to" + " convert all attributes to numeric before reducing the" + " dimension. It preserves the class attribute.\n\n" + "For more information, see:\n\n" + getTechnicalInformation().toString();
    }

    /**
     * Returns an instance of a TechnicalInformation object, containing detailed
     * information about the technical background of this class, e.g., paper
     * reference or book this class is based on.
     * 
     * @return the technical information about this class
     */
    @Override
    public TechnicalInformation getTechnicalInformation() {
        TechnicalInformation result;

        result = new TechnicalInformation(Type.INPROCEEDINGS);
        result.setValue(Field.AUTHOR, "Dmitriy Fradkin and David Madigan");
        result.setValue(Field.TITLE, "Experiments with random projections for machine learning");
        result.setValue(Field.BOOKTITLE, "KDD '03: Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data mining");
        result.setValue(Field.YEAR, "003");
        result.setValue(Field.PAGES, "517-522");
        result.setValue(Field.PUBLISHER, "ACM Press");
        result.setValue(Field.ADDRESS, "New York, NY, USA");

        return result;
    }

    /**
     * Returns the tip text for this property
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String numberOfAttributesTipText() {

        return "The number of dimensions (attributes) the data should" + " be reduced to.";
    }

    /**
     * Sets the number of attributes (dimensions) the data should be reduced to
     * 
     * @param newAttNum the goal for the dimensions
     */
    public void setNumberOfAttributes(int newAttNum) {
        m_k = newAttNum;
    }

    /**
     * Gets the current number of attributes (dimensionality) to which the data will
     * be reduced to.
     * 
     * @return the number of dimensions
     */
    public int getNumberOfAttributes() {
        return m_k;
    }

    /**
     * Returns the tip text for this property
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String percentTipText() {

        return " The percentage of dimensions (attributes) the data should" + " be reduced to  (inclusive of the class attribute). The " + " NumberOfAttributes option is ignored if this option is" + " present or is greater than zero.";
    }

    /**
     * Sets the percent the attributes (dimensions) of the data should be reduced to
     * 
     * @param newPercent the percentage of attributes
     */
    public void setPercent(double newPercent) {
        if (newPercent > 0) {
            newPercent /= 100;
        }
        m_percent = newPercent;
    }

    /**
     * Gets the percent the attributes (dimensions) of the data will be reduced to
     * 
     * @return the percentage of attributes
     */
    public double getPercent() {
        return m_percent * 100;
    }

    /**
     * Returns the tip text for this property
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String seedTipText() {
        return "The random seed used by the random" + " number generator used for generating the random matrix ";
    }

    /**
     * Sets the random seed of the random number generator
     * 
     * @param seed the random seed value
     */
    @Override
    public void setSeed(int seed) {
        m_rndmSeed = seed;
    }

    /**
     * Gets the random seed of the random number generator
     * 
     * @return the random seed value
     */
    @Override
    public int getSeed() {
        return m_rndmSeed;
    }

    /**
     * Returns the tip text for this property
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String distributionTipText() {
        return "The distribution to use for calculating the random matrix.\n" + "Sparse1 is:\n" + " sqrt(3) * { -1 with prob(1/6), \n" + "               0 with prob(2/3),  \n" + "              +1 with prob(1/6) } \n" + "Sparse2 is:\n" + " { -1 with prob(1/2), \n" + "   +1 with prob(1/2) } ";

    }

    /**
     * Sets the distribution to use for calculating the random matrix
     * 
     * @param newDstr the distribution to use
     */
    public void setDistribution(SelectedTag newDstr) {

        if (newDstr.getTags() == TAGS_DSTRS_TYPE) {
            m_distribution = newDstr.getSelectedTag().getID();
        }
    }

    /**
     * Returns the current distribution that'll be used for calculating the random
     * matrix
     * 
     * @return the current distribution
     */
    public SelectedTag getDistribution() {
        return new SelectedTag(m_distribution, TAGS_DSTRS_TYPE);
    }

    /**
     * Returns the tip text for this property
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String replaceMissingValuesTipText() {

        return "If set the filter uses weka.filters.unsupervised.attribute.ReplaceMissingValues" + " to replace the missing values instead of just skipping them.";
    }

    /**
     * Sets either to use replace missing values filter or not
     * 
     * @param t if true then the replace missing values is used
     */
    public void setReplaceMissingValues(boolean t) {
        m_useReplaceMissing = t;
    }

    /**
     * Gets the current setting for using ReplaceMissingValues filter
     * 
     * @return true if the replace missing values filter is used
     */
    public boolean getReplaceMissingValues() {
        return m_useReplaceMissing;
    }

    /**
     * Returns the Capabilities of this filter.
     * 
     * @return the capabilities of this object
     * @see Capabilities
     */
    @Override
    public Capabilities getCapabilities() {
        Capabilities result = super.getCapabilities();
        result.disableAll();

        // attributes
        result.enableAllAttributes();
        result.enable(Capability.MISSING_VALUES);
        result.disable(Capability.STRING_ATTRIBUTES);
        result.disable(Capability.RELATIONAL_ATTRIBUTES);

        // class
        result.enable(Capability.NUMERIC_CLASS);
        result.enable(Capability.DATE_CLASS);
        result.enable(Capability.NOMINAL_CLASS);
        result.enable(Capability.MISSING_CLASS_VALUES);
        result.enable(Capability.NO_CLASS);

        return result;
    }

    /**
     * Sets the format of the input instances.
     * 
     * @param instanceInfo an Instances object containing the input instance
     *                     structure (any instances contained in the object are
     *                     ignored - only the structure is required).
     * @return true if the outputFormat may be collected immediately
     * @throws Exception if the input format can't be set successfully
     */
    @Override
    public boolean setInputFormat(Instances instanceInfo) throws Exception {
        super.setInputFormat(instanceInfo);

        if (instanceInfo.classIndex() >= 0) {
            m_ntob = new weka.filters.supervised.attribute.NominalToBinary();
        } else {
            m_ntob = new weka.filters.unsupervised.attribute.NominalToBinary();
        }

        m_replaceMissing = null;
        m_OutputFormatDefined = false;
        if (getReplaceMissingValues()) {
            m_replaceMissing = new ReplaceMissingValues();
            m_replaceMissing.setInputFormat(instanceInfo);
            if (m_ntob.setInputFormat(m_replaceMissing.getOutputFormat())) {
                setOutputFormat();
                return true;
            } else {
                return false;
            }
        }

        if (m_ntob.setInputFormat(instanceInfo)) {
            setOutputFormat();
            return true;
        } else {
            return false;
        }
    }

    /**
     * Input an instance for filtering.
     * 
     * @param instance the input instance
     * @return true if the filtered instance may now be collected with output().
     * @throws IllegalStateException if no input format has been set
     */
    @Override
    public boolean input(Instance instance) throws Exception {

        if (getInputFormat() == null) {
            throw new IllegalStateException("No input instance format defined");
        }
        if (m_NewBatch) {
            resetQueue();
            m_NewBatch = false;
        }

        if ((m_OutputFormatDefined) && ((!m_useReplaceMissing) || isFirstBatchDone())) {
            if (m_replaceMissing != null) {
                m_replaceMissing.input(instance);
                instance = m_replaceMissing.output();
            }
            m_ntob.input(instance);
            instance = m_ntob.output();

            push(convertInstance(instance), false);
            return true;
        }
        bufferInput(instance);
        return false;
    }

    /**
     * Signify that this batch of input to the filter is finished.
     * 
     * @return true if there are instances pending output
     * @throws NullPointerException if no input structure has been defined,
     * @throws Exception            if there was a problem finishing the batch.
     */
    @Override
    public boolean batchFinished() throws Exception {

        if (getInputFormat() == null) {
            throw new NullPointerException("No input instance format defined");
        }

        Instances insts = getInputFormat();
        if (m_useReplaceMissing) {
            insts = Filter.useFilter(insts, m_replaceMissing);
        }
        insts = Filter.useFilter(insts, m_ntob);

        if (!m_OutputFormatDefined) {
            setOutputFormat();
        }

        for (Instance instance : insts) {
            push(convertInstance(instance), false); // No need to copy
        }

        flushInput();
        m_NewBatch = true;
        m_FirstBatchDone = true;

        return (numPendingOutput() != 0);
    }

    /** Sets the output format */
    protected void setOutputFormat() throws Exception {

        Instances currentFormat = m_ntob.getOutputFormat();

        if (m_percent > 0) {
            m_k = (int) ((getInputFormat().numAttributes() - 1) * m_percent);
        }

        ArrayList<Attribute> attributes = new ArrayList<Attribute>();
        for (int i = 0; i < m_k; i++) {
            attributes.add(new Attribute("K" + (i + 1)));
        }
        if (getInputFormat().classIndex() > -1) {
            attributes.add((Attribute) getInputFormat().classAttribute().copy());
        }

        Instances newFormat = new Instances(currentFormat.relationName(), attributes, 0);
        if (getInputFormat().classIndex() > -1) {
            newFormat.setClassIndex(attributes.size() - 1);
        }

        m_random = new Random(m_rndmSeed);

        m_rmatrix = new double[m_k][currentFormat.numAttributes()];
        if (m_distribution == GAUSSIAN) {
            for (int i = 0; i < m_rmatrix.length; i++) {
                for (int j = 0; j < m_rmatrix[i].length; j++) {
                    m_rmatrix[i][j] = m_random.nextGaussian();
                }
            }
        } else {
            boolean useDstrWithZero = (m_distribution == SPARSE1);
            for (int i = 0; i < m_rmatrix.length; i++) {
                for (int j = 0; j < m_rmatrix[i].length; j++) {
                    m_rmatrix[i][j] = rndmNum(useDstrWithZero);
                }
            }
        }

        m_OutputFormatDefined = true;
        setOutputFormat(newFormat);
    }

    /**
     * converts a single instance to the required format
     * 
     * @param instance the instance to convert
     * @return the converted instance
     */
    protected Instance convertInstance(Instance instance) throws Exception {

        double vals[] = new double[outputFormatPeek().numAttributes()];

        for (int j = 0; j < m_k; j++) {
            for (int i = 0; i < instance.numValues(); i++) {
                int index = instance.index(i);
                if (index != instance.classIndex()) {
                    double value = instance.valueSparse(i);
                    if (!Utils.isMissingValue(value)) {
                        vals[j] += m_rmatrix[j][index] * value;
                    }
                } else {
                    vals[m_k] = instance.valueSparse(i);
                }
            }
        }
        return new DenseInstance(instance.weight(), vals);
    }

    private static final int weights[] = { 1, 1, 4 };
    private static final int vals[] = { -1, 1, 0 };
    private static final int weights2[] = { 1, 1 };
    private static final int vals2[] = { -1, 1 };
    private static final double sqrt3 = Math.sqrt(3);

    /**
     * returns a double x such that <br/>
     * x = sqrt(3) * { -1 with prob. 1/6, 0 with prob. 2/3, 1 with prob. 1/6 }
     * 
     * @param useDstrWithZero
     * @return the generated number
     */
    protected double rndmNum(boolean useDstrWithZero) {
        if (useDstrWithZero) {
            return sqrt3 * vals[weightedDistribution(weights)];
        } else {
            return vals2[weightedDistribution(weights2)];
        }
    }

    /**
     * Calculates a weighted distribution
     * 
     * @param weights the weights to use
     * @return
     */
    protected int weightedDistribution(int[] weights) {
        int sum = 0;

        for (int weight : weights) {
            sum += weight;
        }

        int val = (int) Math.floor(m_random.nextDouble() * sum);

        for (int i = 0; i < weights.length; i++) {
            val -= weights[i];
            if (val < 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Main method for testing this class.
     * 
     * @param argv should contain arguments to the filter: use -h for help
     */
    public static void main(String[] argv) {
        runFilter(new RandomProjection(), argv);
    }
}
